The invention relates to secure communications. More particularly the invention relates to cryptographic communication systems and methods for use in data-processing systems to enhance security. The proposed public-key cryptosystem is secure against a lunch-time attack and an adaptive chosen ciphertext attack.
Secrecy and security are important factors in today""s computationally connected world. Transmitted information is restricted to an intended receiver and not suitable for everyone. For assuring secure and authenticated communications, cryptographic methods arc help- and useful. A cryptographic system is a system for sending a message from a sender to a receiver over a medium so that the message is xe2x80x98securexe2x80x99. That means, only the intended receiver can recover the message. The cryptographic system converts the message, also referred to as plaintext, into an encrypted format, known as ciphertext. The encryption is accomplished by manipulating or transforming the message using a cipher key or keys. The receiver decrypts the message by converting the ciphertext back to plaintext. This is performed by reversing the manipulation or transformation process using the cipher key or keys. Such an encrypted transmission is secure, so long as only the sender and the receiver have knowledge of the cipher key. Several cryptographic systems have been proposed in the past such as public-key cryptosystems. In general, an information used with an algorithm to encrypt and decrypt a message is called a key. The public key cryptosystem uses two keys, one private and one public, which are related to each other. Hence, in the public-key cryptosystem, the private key is always linked mathematically to the public key. Therefore, it is always possible to attack a public-key system by deriving the private key from the public key. Typically, the defense against this is to make the problem of deriving the private key from the public key as difficult as possible.
Diffie-Hellman:
A first public-key cryptographic scheme was published by Diffie and Hellman, xe2x80x9cNew Directions in Cryptographyxe2x80x9d, IEEE Trans. Inform. Theory, vol. IT-22, pp. 644-654, November 1976. This scheme, also referred to as Diffie-Hellman key agreement, describes a public-key system based on discrete exponential and logarithmic functions and is primarily used for public-key exchange and public-key cryptosystems. The basis for the technique is the difficulty of calculating logarithms in modular arithmetic. Say A and B wish to establish a key. A sends B a number g, a modulus p and the number h1=ge1 mod(p), where e1 is a large number. B then sends back to A the number h2=ge1 mod(p). They each then use the number k=g(e1 e2)=h1e2=h2e1 mod(p) as the private key. Any adversary must be able to calculate either e1 from g, h1 or e2 from g, h2. This is believed to be very hard for large enough values of g and p, since no general, fast algorithms are known for solving a discrete logarithm function.
RSA:
Another public-key cryptosystem is disclosed in xe2x80x9cOn Digital Signatures and Public key Cryptosystemsxe2x80x9d, Commun. Ass. Comput. Mach., vol. 21, pp. 120-126, 1979, by R. L. Rivest, A Shamir, and L. M. Adelman. The so-called RSA scheme is based on the fact that it is easy to generate two large primes and multiply them, whereas it is much more difficult to factor the result, that is, to derive the large primes from their product. Therefore it should be computationally infeasible to perform this derivation. The product can therefore be made public as part of the enciphering key without compromising the primes that constitute the deciphering key.
ElGamal:
The publication xe2x80x9cA Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithmsxe2x80x9d by T. ElGamal in the IEEE Trans. Inform. Theory, vol. IT-31, pp. 469-472, 1985, proposes a further public-key cryptosystem which implements the Diffie-Hellman key agreement. The ElGamal scheme comprising a secret key z and a public key h can be described in a simple way as the following. A message m can be encoded as elements of a cryptographic group G. The secret key z can be chosen at random from a set of numbers modulo q, denoted as Zq. The public key h is calculated by h=gz, whereby g is also chosen from the group G at random. The encryption starts by choosing a random element r in Zq. A ciphertext comprising u and e is derived by u=gr and e=hrm. This ciphertext can be decrypted to the message m by m=e/uz. The security of the ElGamal encryption scheme relies on the difficulty of recomputing discrete logarithms, but the ElGamal encryption is only secure against passive attacks and not secure against chosen ciphertext attacks. In particular, the ElGamal encryption scheme is trivially malleable. Thus, if u, e encrypts m, then u, ea encrypts ma.
All mentioned schemes are insecure against active attacks, in which an attacker or adversary can inject chosen messages into the stream of data and observe the resulting behaviors. An xe2x80x9cadaptive chosen ciphertext attackxe2x80x9d is the strongest known form of this kind of attack and is generally accepted to be the most aggressive kind of attack that any cryptosystem should be expected to withstand. Such an attack is one in which an adversary has access to a xe2x80x9cdecryption oraclexe2x80x9d, e.g. a server, allowing the adversary to decrypt ciphertexts of his choice. The word xe2x80x9cadversaryxe2x80x9d is commonly used in cryptography to refer to an opponent, an enemy, or any other mischievous person that desires to compromise one""s security. Typically, one distinguishes between a weak form of attack, known as a lunch-time attack, and the strongest possible form, the adaptive chosen ciphertext attack. In the lunch-time attack, the adversary queries the decryption oracle a number of times, after which the adversary obtains the target ciphertext that the adversary wishes to cryptanalyze, and is not allowed to query the decryption oracle further. In an adaptive attack, the adversary may continue to query the decryption oracle after obtaining the target ciphertext, whereby the adversary repeats the following process: he sends requests to the software or hardware units implementing the cryptographic scheme, observes the responses, and based on the responses constructs and sends more requests, with the aim of eventually breaking the scheme. In fact the adversary may send any ciphertext to the decryption oracle, except the target ciphertext. D. Bleichenbacher discloses in xe2x80x9cChosen ciphertext attacks against protocols based on RSA encryption standard PKCS #1xe2x80x9d, Advances in Cryptology-Crypto ""98, pp. 1-12, 1998, design flaws in the widely used Internet security protocol SSL (Secure Socket Layer). Bleichenbacher""s attack is a direct attack on what is supposed to be secure: the security protocol and the underlying encryption system. As mentioned above, such an adversary does more than just eavesdrop: he plays an active rule, sending carefully crafted encryptions to the SSL server, and then observes how the server responds to these encryptions. Based on these observations, the adversary can crack the code.
For many years, no public-key system was shown to be secure under a chosen ciphertext attack. M. Naor and M. Yung presented the first scheme provably secure against lunch-time attacks in their publication xe2x80x9cPublic-key cryptosystems provably secure against chosen ciphertext attacksxe2x80x9d, in 22nd Annual ACM Symposium on Theory of Computing, pages 427-437, 1990. Subsequently, D. Dolev, C. Dwork, and M. Naor presented in their publication xe2x80x9cNon-malleable cryptographyxe2x80x9d, in 23rd Annual ACM Symposium on Theory of Computing, pages 542-552, 1991, a scheme which is secure against adaptive chosen ciphertext attack. All of the known schemes provably secure under standard intractability assumptions are completely impractical, as they rely on general and expensive constructions for non-interactive zero-knowledge proofs.
I Damgard. proposed in the publication xe2x80x9cTowards practical public key cryptosystems secure against chosen ciphertext attacksxe2x80x9d, in Advances in Cryptology-Crypto ""91, pages 445-456, 1991, a practical scheme that he conjectured to be secure against lunch-time attacks; however, this scheme is not known to be provably secure, and is in fact demonstratably insecure against adaptive chosen ciphertext attack.
Y. Zheng and J. Seberry proposed in their publication xe2x80x9cPractical approaches to attaining security against adaptively chosen ciphertext attacksxe2x80x9d, in Advances in Cryptology-Crypto ""92, pages 292-304, 1992, practical schemes that are conjectured to be secure against chosen ciphertext attack, but again, no proof based on standard intractability assumptions is known.
C. H. Lim and P. J. Lee also proposed in their publication xe2x80x9cAnother method for attaining security against adaptively chosen ciphertext attacksxe2x80x9d, in Advances in Cryptology-Crypto ""93, pages 420-434, 1993, practical schemes that were later broken by Y. Frankel and M. Yung, which was described in xe2x80x9cCryptanalysis of immunized LL public key systemsxe2x80x9d, in Advances in Cryptology-Crypto ""95, pages 287-296, 1995.
In a different direction, M. Bellare and P. Rogaway have presented in their publication xe2x80x9cRandom oracles are practical: a paradigm for designing efficient protocolsxe2x80x9d, In First ACM Conference on Computer and Communications Security, 1993, and xe2x80x9cOptimal asymmetric encryptionxe2x80x9d, in Advances in Cryptology-Crypto ""94, pages 92-111, 1994, practical schemes that are provably secure against adaptive chosen ciphertext attack in an idealized model of computation where a hash function is represented by a random oracle. While a proof of security in the random oracle model is certainly preferable to no proof at all, a proof in the xe2x80x9creal worldxe2x80x9d would be even better.
R. Canetti, O. Goldreich, and S. Halevi showed in the publication xe2x80x9cThe random oracle model, revisitedxe2x80x9d, in 30th Annual ACM Symposium on Theory of Computing, 1998, that there are cryptographic schemes that are secure in the random oracle model, but insecure in the real worldxe2x80x94no matter what hash function is chosen. It is not yet clear what the implications of these results are.
While there are several provably secure encryption schemes in the literature, they are all impractical. Also, there have been several practical cryptosystems that have been proposed, but none of them has been proven secure under standard intractability assumptions.
All currently commercially available cryptosystems are potentially vulnerable to active attacks. Therefore it is an object of the present invention to provide a secure cryptosystem in order to overcome the disadvantages of the prior art.
It is another object of the present invention to provide a public-key cryptosystem that is secure against an attack such as a lunch-time attack.
It is still another object of the present invention to provide a public-key cryptosystem that is secure against an adaptive chosen ciphertext attack.
It is a further object of the present invention to achieve a public-key cryptosystem that is secure and practical at the same time.
The present invention improves the security of encrypted data or information by using a practical public-key cryptosystem that is able to resist adaptive attacks. The disclosed scheme does not leak any information about the secret of the used key. Therefor the scheme generates an extended private key and public key. A message m, also referred to as plaintext, can be encrypted to obtain to a ciphertext t by using the public key. This ciphertext t can be transmitted over an insecure channel, e.g. the Internet. Only a recipient with the right private key is able to decrypt the ciphertext t. But before a decryption starts, a simple verification of the ciphertext t is performable. Such a verification allows to prove the legitimacy of the ciphertext t. That means, the ciphertext t is investigated and can be either decrypted back to the plaintext if the ciphertext t is properly constructed, ie. the ciphertext is legitimate or valid, or can be rejected if a chosen ciphertext is revealed as having been fed, ie. the ciphertext is illegitimate or invalid. The rejection has the advantage that an adversary can not submit arbitrary ciphertexts and therefore the adversary gets no information about other encrypted data. Hence, a lunch-time attack or even an adaptive chosen ciphertext attack can not only be discovered, but such an attack can be prevented altogether. It further turns out that by rejecting all illegitimate ciphertexts, no information about the private key is leaked, which effectively neutralizes the chosen ciphertext attack and shows that the plaintext can be hidden perfectly.
The disclosed public-key scheme brings the advantage that adaptive attacks are useless for the attacker since no information is leaked. Therefore, by using the present public-key cryptosystem, a secure communication can be guaranteed also when sensitive or personal information, such as credit card details, authorizations, passwords, PIN codes, and so forth, are involved and transmitted. For example, e-commerce transactions which travel across the world can be achieved in a private and secure manner.
Security against adaptive chosen ciphertext attack also implies non-malleability, meaning that an adversary cannot take an encryption of some plaintext and transform it into an encryption of a different plaintext that is related to the original plaintext. It is another advantage of the present public-key scheme that it is not malleable.
The disclosed public-key scheme can be used not only for privacy, ie. encryption, but also for authentication.
The present system is secure against a lunch-time attack since the system is practical using a few exponentiations over a group. Further, by the application of a hash function, the system is secure against an adaptive chosen ciphertext attack. Moreover, the proof of security bases on standard intractability assumptions, namely, the hardness of the Diffie-Hellman decision problem in the underlying group, and the collision intractability of the hash function.
The hardness of the Diffie-Hellman decision problem, also referred to as DDH problem (Decisional Diffie-Hellman problem), is essentially equivalent to the security of the basic ElGamal encryption scheme against passive adversaries. Thus, with the additional assumption of a collision-resistant hash function and some computation, security against adaptive chosen ciphertext attack is achieved, whereas the basic ElGamal scheme is completely insecure against adaptive chosen ciphertext attack.
A public-key cryptosystem is proposed which is secure and practical at the same time.
The following are informal definitions to aid in the understanding of the description.
Group: A group in the cryptographic sense is an algebraic system (G,*) consisting of a set of elements or numbers and a group operation (*) with some specified properties, where (*) is associative, has a neutral element, and where every element in G has an inverse element.
The choice of the symbol (*) is arbitrary. In fact, the operation of most groups is denoted by either + or xe2x80xa2, and such groups are referred to as additive or multiplicative group, respectively.
Finite group: A group G is called finite if it contains only finitely many elements. The number of elements in a finite group is called its order.
For example, for any positive integer n, a set Zn consists of the integers 0, . . . , nxe2x88x921, and it forms a group under the operation of addition modulo n. Moreover, the subset of Zn consisting of those integers relatively prime to n forms a group under multiplication modulo n, and is denoted Zn*. In particular, if p is prime, then Zn* consists of {1, . . . , pxe2x88x921}, and is a group with pxe2x88x921 elements.
Hash function: A hash function is a computationally efficient function mapping binary strings of arbitrary length to binary strings of some fixed length.
Collision resistant hash functions: A family of hash functions is collision resistant if given a random hash function H in the family, it is infeasible to find a collision, ie., two strings xxe2x89xa0y such that H(x)=H(y).